A "packet" is a discrete quantity of information used in the communication of data. The transmission of packets between users may be greatly enhanced by packet switching using a packet switched network. The concept of packet switching is based on the ability of modern, high-speed digital computers to manipulate information packets that are transmitted between such computers.
As shown in FIG. 1, in a typical prior art packet switched network 11, a plurality of nodes 13 are connected by communications lines 15. Each node contains a high-speed digital computer. Information sent from a transmitter 17 to a receiver 19 may travel over many different possible paths. Each path is a route of the packet over a plurality of communication lines 15. Typically, some communication lines 15 will be busier than others. Therefore, by dividing the information into packets, the nodes can efficiently use those communication lines which are readily available. For example, information "A B C D E", which is sent from the transmitter 17 to the receiver 19, is initially parsed into packets (the packets being the individual letters--"A", "B", "C", "D" and "E"). In this example, the packet size is one letter; however, the size of a packet may vary from one packet switched network to another. Within a particular packet switched network, all packets are the same size.
The packets are then transferred along differing paths. For example, the packet "C" is transmitted along a roundabout path which passes through six nodes before arrival at the receiver 19. In contrast, packet "E" is transmitted along a direct path passing through only three nodes. Each node 13 determines the most efficient path along which to transfer the packets. The receiver 19, after receiving the transmitted packets, recombines the packets to form the original transmitted information. The receiver uses information about the packets' size and identification, which may be included in the packets themselves, and a knowledge of the parsing scheme to perform the recombination.
Typically, the packets move around the packet switched network, from node to node, on a hold-and forward basis; each node, after receiving a packet, "holds" a copy of the packet in temporary storage until the node is sure that the packet has been received properly by the next node or by the end user. The copy of the packet is destroyed when the node is confident that the packet has been relayed successfully. The movement of the packets is called packet switching. By moving the packets through the network in nearly real time, the nodes can adapt their operation quickly in response to changing traffic patterns or failure of part of the network facility.
A packet switched network is characterized by several parameters. The first of these is packet size. As noted above, packet size may be through of as the amount of data carried within each packet. Another parameter which characterizes a packet switched network is the channel capacity of the network. The channel capacity may be defined as the maximum amount of information a particular communications line may handle or, in other words, the maximum number of packets which can be transferred over the communications line in a given time period. Channel capacity may be expressed as a bit rate capacity.
Using a packet switched network, communication resources may be efficiently used. Further, packet switching can be adapted to a wide range of user services. Presently, packet switching is used primarily in connection with computer and data communications. However, its effectiveness for voice, video and other wide-band telecommunication services has been demonstrated. As advanced data processing techniques improve the computer processors that form the nodes of packet switched networks, use of packet switched networks will undoubtedly become widespread.
However, packet switched networks also introduce some special problems in the communications area. One of the major obstacles of packet switched networks is the potential loss of packets. Packet loss can occur at the transmitter 17 if the number of packets generated is in excess of the transmission capacity, or at the receiver 19 if certain packets arrive after an exceptionally long delay. Moreover, packets can be lost within the network due to transmission impairment such as switch failure or transmission channel noise. Packet loss is particularly prevalent in video image transmissions. Typically, video images contain a much larger amount of information than other types of signals, such as audio signals. Therefore, video images must be transmitted at high densities which translate into high bit rates. Because of the high bit rates involved, packet loss occurs more frequently. Such loss may significantly affect the quality of video image transmissions.
One method that is used to avoid the loss of transmission quality, resulting from loss of packets, of a video image transmission is the use of a reliable source coding scheme. In order to guarantee transmission quality in a packet switched network, where packet loss is considered inevitable, source coding schemes should be designed in such a way that the distortion caused by packet loss is minimized, while the potential for recombining the original transmitted signal is maximized. Ideally, the source coding scheme at the transmitter and recombination at the receiver ought to be such that the original signal can be exactly recombined using the packets in the absence of quantization noise, transmission noise, and packet loss--the so-called "perfect reconstruction requirement."
Several methods of splitting a signal into packets exist which satisfy the perfect reconstruction requirement. One of these methods is the sub-band analysis/synthesis method. Conceptually, this source coding scheme consists of separating the original signal into different frequency components. Each separate frequency component is referred to as a sub-band signal. The separation of the original signal into sub-band signals is accomplished by inputting the signal into a number of analysis filters. The analysis filters output the sub-band signals. The sub-band signals are then transmitted as separate packets. The receiver, upon receipt of the packets, can form a reconstruction of the original signal by recombining the frequency components. This is typically done by the use of synthesis filters at the transmitter that are matched to the analysis filters at the transmitter. A system that uses this coding technique is referred to as a sub-band transmission network.
Because the loss of packets is considered inevitable, various missing packet recovery techniques have been suggested. These techniques may be divided into two groups: retransmission and reconstruction. A technique in the first group requests retransmission upon the detection of a lost packet. However, this technique will introduce random delay in the transmission and decrease transmission speed. A technique in the second group attempts to recover the lost packets based upon the characteristics of other correctly received packets. The success of the reconstruction relies upon the correlation between the lost packets and the received packets. Perfect reconstruction is unlikely unless the lost packets are completely correlated with the received packets. Correlation is a measure of the relatedness of two signals; for example, two successive frames in a video sequence will likely be well correlated.
The prior art as it relates to the reconstruction techniques consists primarily of simple substitution or interpolation. In these two methods the lost packets are replaced with or interpolated from the temporary or spatially adjacent received packets, respectively. The present invention addresses the problem of reconstruction in a manner that provides for a high-quality reconstruction. Further, the present invention provides a reliable method for information recovery in packet switched networks.